package algorithm;

/**
 * 递归实现迷宫回溯问题
 *
 * @author hck
 */
public class RecursiveMaze {
    /**
     * 未走过
     */
    private static final int NONE = 0;
    /**
     * 墙
     */
    private static final int WALL = 1;
    /**
     * 通路可以走
     */
    private static final int PASSED = 2;
    /**
     * 该点往四面走都是死路
     */
    private static final int IMPASSE = 3;

    public static void main(String[] args) {
//        test77Map();
        test99Map();
    }

    /**
     * 测试 9*9 迷宫
     * <p>
     * 1 1 1 1 1 1 1 1 1
     * 1       1   1   1
     * 1   1   1       1
     * 1   1   1   1   1
     * 1   1 1 1   1   1
     * 1       1   1   1
     * 1   1       1   1
     * 1   1   1   1   1
     * 1 1 1 1 1 1 1 1 1
     */
    private static void test99Map() {
        int[][] map = new int[9][9];
        setSurroundWall(map);
        map[2][2] = WALL;
        map[3][2] = WALL;
        map[4][2] = WALL;
        map[6][2] = WALL;
        map[7][2] = WALL;
        map[4][3] = WALL;
        map[1][4] = WALL;
        map[2][4] = WALL;
        map[3][4] = WALL;
        map[4][4] = WALL;
        map[5][4] = WALL;
        map[7][4] = WALL;
        map[1][6] = WALL;
        map[3][6] = WALL;
        map[4][6] = WALL;
        map[5][6] = WALL;
        map[6][6] = WALL;
        map[7][6] = WALL;
        printMap(map);

        System.out.println("---------------");
        goToAccordingDRUL(map, 1, 1, 7, 7);

        printMap(map);
    }

    /**
     * 测试 7*7 迷宫
     * <p>
     * 1 1 1 1 1 1 1
     * 1   1       1
     * 1   1   1   1
     * 1   1   1   1
     * 1   1   1   1
     * 1       1   1
     * 1 1 1 1 1 1 1
     */
    private static void test77Map() {
        int[][] map = new int[7][7];
        setSurroundWall(map);
        map[1][2] = WALL;
        map[2][2] = WALL;
        map[3][2] = WALL;
        map[4][2] = WALL;
        map[2][4] = WALL;
        map[3][4] = WALL;
        map[4][4] = WALL;
        map[5][4] = WALL;
        printMap(map);
        System.out.println("-----------");
        goToAccordingDRUL(map, 1, 1, 5, 5);
        printMap(map);
    }


    /**
     * 测试4*4迷宫
     */
    private static void test44Map() {
        int[][] map = new int[4][4];
        setSurroundWall(map);
        //  这里测试走不通路start
//        map[1][2] = WALL;
//        map[2][2] = WALL;
        //  这里测试走不通路end
        printMap(map);
        //  从(1,1) 走到(2,2)
        goToAccordingDRUL(map, 1, 1, 2, 2);
        System.out.println("----------------");
        printMap(map);
    }

    private static void setSurroundWall(int[][] map) {
        for (int i = 0; i < map.length; i++) {
            //  第一行置为墙
            map[0][i] = WALL;
            //  最后一行置为墙
            map[map.length - 1][i] = WALL;
            //  第一列置为墙
            map[i][0] = WALL;
            //  最后一列置为墙
            map[i][map.length - 1] = WALL;
        }
    }

    /**
     * 走到下一个点
     * 按照下右上左的顺序.走不通再返回
     *
     * @param map map
     * @param x   x行
     * @param y   y列
     * @return 是否是通路
     */
    private static boolean goToAccordingDRUL(int[][] map, int x, int y, int endX, int endY) {
        if (map[endX][endY] == PASSED) {
            //  走到终点
            return true;
        }

        if (map[x][y] == NONE) {
            //  如果当前点没有走过
            map[x][y] = PASSED;
            //  向下走
            if (goToAccordingDRUL(map, x + 1, y, endX, endY)) {
                return true;
            }
            //  向右走
            if (goToAccordingDRUL(map, x, y + 1, endX, endY)) {
                return true;
            }
            //  向上走
            if (goToAccordingDRUL(map, x - 1, y, endX, endY)) {
                return true;
            }
            //  向左走
            if (goToAccordingDRUL(map, x, y - 1, endX, endY)) {
                return true;
            }
            map[x][y] = IMPASSE;
        }
        return false;
    }

    /**
     * 打印当前迷宫
     *
     * @param map
     */
    private static void printMap(int[][] map) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 0) {
                    System.out.print("  ");
                    continue;
                }
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}
